<TITLE>prob022: bus driver scheduling</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob022: bus dirver scheduling</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.scs.leeds.ac.uk/suniel/work.html">
          <B>Suniel Curtis</B></A> 
          <ADDRESS><a href="mailto:suniel@scs.leeds.ac.uk">
          suniel@scs.leeds.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT> 
Bus driver scheduling can be formulated as a set paritioning problem.
We propose 12 set partitioning problems derived from small bus driver scheduling problems. 
These consist of a given set of tasks (pieces of work) to cover and a large set of possible shifts,
where each shift covers a subset of the tasks and has an associated cost.  We must select a subset of
possible shifts that covers each piece of work once and only once: this is called a partition.  Further,

<p>
In the driver scheduling (unlike air crew scheduling) the main aim is to reduce the
number of shifts used in the solution partition and the total cost of the partition is secondary.  To
simplify the problem we have made the cost of each shift the same.  This means that to minimise the

<p>
The problems come from four
different bus companies: Reading (r1 to r5a), CentreWest Ealing area (c1, c1a, c2), the former London
Transport (t1 and t2). The problems have differing regulations and features (e.g. urban and short
distance rural bus schedules can have very different features).  Note that r1 and r1a are the same
problem, but have different numbers of generated shifts.  Similarly with the problems: c1, c1a and r5,
r5a. Problems are presented in the same format as the set partitioning examples in
ORLIB.
The first line gives the number of rows (pieces of work), columns (shifts) and the minimum number of
columns need for a partition. Then each line after that corresponds to one column.  It starts with the
cost (which is always 1 in our case) then the number of rows it covers, followed by the rows it covers.





<p>

</TT>
























<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page. 

